Représentation des nombres

Table des matières

1. Représentation binaire de la mémoire

En informatique toute information est conservée sous forme binaire. La mémoire d'un ordinateur (il y en a plusieurs types) est une collection de plusieurs milliards de systèmes physiques qui ont chacun deux états possibles. Chacun de ces petits systèmes physiques représente ce qu'on appelle un bit. Un des deux états physiques signifie que le bit vaut $1$, l'autre état que le bit vaut $0$.

Ces bits sont regroupés en octets (bytes en anglais) constitués de 8 bits chacun. Ces octets sont eux-mêmes regroupés en mots (words en anglais). La taille d'un mot dépend de l'architecture de la machine. Pour les ordinateurs personnels modernes (et les téléphones), un mot est constitué de 64 bits (ou 8 octets). Il y a une dizaine d'années, les mots étaient constitués de 32 bits. Un mot de mémoire est l'objet naturel que le processeur lit et sur lequel il fait des opérations.

L'objectif de ce chapitre est d'expliquer comment un mot (c'est-à-dire 64 bits) peut être utilisé pour représenter un entier positif (non signé), un entier relatif (signé) ou un nombre à virgule (un flottant). Cette représentation se fait via le choix d'un encodage.

Types de mémoire d'un ordinateur

En pratique, l'ordinateur a plusieurs types de mémoires :

  • la mémoire du disque dur ($\simeq$ 1000 Go), auquel l'accès est lent (lecture d'un Mo en $1\,ms$ pour un HDD, et $50\,\mu s$ pour un SSD).

  • la mémoire vive, RAM, ($\simeq$ 8 Go), (lecture d'un Mo en $4\,\mu s$).

    Quand on «ouvre» un fichier, son contenu est copié depuis le disque dur dans la mémoire vive, pour que le processeur puisse y accéder.

    C'est aussi ici que «vivent» les variables/listes que l'on utilise.

  • les différents caches du processeur ($\simeq$ 1 Mo). Accès rapide (de l'ordre de quelques nanosecondes).

    Quand une variable va être utilisée à plusieurs reprises, elle est copiée de la mémoire vive dans un cache.

Utilisation de la mémoire.

  • Chaque octet (8 bits) de la mémoire peut prendre $2^8 = 256$ valeurs différentes.
  • Chaque mot (64 bits, 8 octets) peut prendre $2^{64}\simeq 20\times 10^{18}$ valeurs différentes.

Un mot mémoire peut être utilisé pour représenter différents objets élémentaires, comme un entier, un flottant, où une adresse mémoire. Cette représentation repose sur le choix d'un encodage qui décrit comment interpréter une suite de 64 bits (0010100…01) en un entier, ou un flottant.

Avec une telle représentation des entiers (un entier = un mot de mémoire), sur une machine de 8 Go de RAM, quelle est la taille maximale théorique d'une liste d'entiers ?

En pratique, les entiers pythons ont une représentation plus compliquée, et prennent 4 fois plus de place.

L'encodage ASCII permet d'encoder 256 caractères comme les caractères de bases : a-z, A-Z, 0-9, la ponctuation, les espaces et le retour à la ligne sur $8$ bits (un octet). On peut imaginer qu'un fichier texte n'utilisant que ces caractères soit constitué en mémoire de la suite des codes ASCII de ses caractères, chacun prenant un octet de mémoire.

D'autres encodages, comme l'encodage UTF-8, permettent de représenter plus de caractères (dont les émoticônes), en utilisant plusieurs octets.

Le codage RGB (Red Green Blue) permet d'encoder une couleur sur $3$ octets. Chaque octet encode un entier de $\db{0, 255}$ et le triplet d'entiers $(r,g,b)$ décrit la couleur selon chaque couleur primaire (des valeurs plus élevées donne une couleur plus claire).

La résolution 1080p d'une image correspond à 1080 pixels de haut et 1920 pixels de large. Si on encode une image à une résolution 1080p par un tableau à deux dimensions contenant pour chaque pixel le code RGB de la couleur de ce pixel, quelle est la taille (en octets) de l'image ? 1

2. Aspect théorique : écriture binaire

2.1. Définition

Soit $b\geq 2$. Pour tout $n\in\N^*$ il existe $k\in\N$ et $a_0,\dots,a_k\in\db{0,b-1}$ tels que $$(*) \quad n = \sum_{i=0}^k a_i b^i \et a_k\neq 0.$$ Cette écriture est unique est appelée la décomposition de $n$ en base $b$. La notation $n = \underline{a_k\dots a_0}_b$ est équivalente à $(*)$.

On montre l'existence par récurrence forte. Si $n\in\db{1,b-1}$, on peut simplement écrire $n = n b^0$.

Soit $n\geq b$. On suppose que tout entier $1\leq m\lt n$ admet une telle décomposition.

On écrit la division euclidienne de $n$ par $b$ : il existe $q\in\N$ et $r\in\db{0,b-1}$ tels que $n = bq + r$. Comme $n\geq b$, nécessairement $q\geq 1$, et on peut lui appliquer l'hypothèse de récurrence : il existe $k$, et des entiers tels que $$q = a_0 b^0 + a_1 b^1 + \dots + a_k b^k,$$ mais alors $$n = bq + r = r b^0 + a_0 b^1 + \dots + a_k b^{k+1},$$ d'où l'existence de la décomposition pour $n$.

Pour l'unicité : l'écriture $n = \sum_{i=0}^k a_i b^i$ implique $a_0 \equiv n [b]$, donc $a_0$ est le reste de la division euclidienne de $n$ par $b$, puis en retirant $a_0$, et divisant par $b$, on obtient $a_1\equiv \frac{n-a_0}{b} [b]$, etc.

Pour $b = 2$, on a $a_i\in \db{0,1}$, donc $a_i\in \{0,1\}$, et $n = \sum_{i=0}^k a_i 2^i$ revient à écrire $n$ comme somme de puissances de $2$ distinctes. On peut la déterminer en appliquant un algorithme glouton.

La décomposition en base $2$ de $19$ est $19 = 16 + 2 + 1 = 1 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0$. On note $19 = \underline{10011}_2$.

Donner les décompositions binaires de

  1. 3
  2. 14
  3. $2^n$
  4. $2^n + 1$
  5. $2^n - 1$

Soit $b\geq 2$ et $n\in\N^*$. Le nombre de chiffres de la décomposition de $n$ en base $b$ est $\lfloor \log_b n\rfloor + 1$, où $\log_b$ est le logarithme en base $b$, défini par $\log_b n = \frac{\ln n}{\ln b}$.

Si $n = \sum_{i=0}^k a_i b^i$, avec $a_i \in \db{0,b-1}$ et $a_k\neq 0$, on a $$b^k \leq n\leq \sum_{i=0}^k (b-1) b^i = b^{k+1} - 1.$$

Donc $b^k \leq n \lt b^{k+1}$. En appliquant $\log_b$ (croissante) à ces inégalités, on obtient $k \leq \log_b n \lt k+1$, donc $\lfloor \log_b n\rfloor = k$.

Le nombre de chiffres de la décomposition est $k+1 = \lfloor \log_b n \rfloor + 1$.

En particulier, le nombre de chiffres (de l'écriture décimale) d'un entier strictement positif est $\lfloor \log n\rfloor + 1$

2.2. Calcul d'un entier à partir de sa décomposition

Écrire une fonction evalue_decomp qui prend en arguments une liste $\texttt{l} = [a_0,a_1,\dots,a_k]$ et un entier b, et renvoie l'entier $n = \sum_{i=0}^k a_i b^i$ dont l est la liste des chiffres dans sa représentation en base b (avec les chiffres de plus petits poids en premier).

Le boutisme (endianness en anglais) désigne l'ordre dans lequel on représente les chiffres (ou les bits en base $2$). Soit du chiffre de plus petit exposant au plus grand comme dans l'exemple précédent (représentation petit-boutiste), soit l'inverse, comme dans notre représentation décimale usuelle. Les architectures usuelles sont gros-boutistes.

L'entier $\underline{342}_{5}$ est représenté par la liste $[3,4,2]$ en représentation gros-boutiste, et par la liste $[2, 4, 3]$ en petit-boutiste.

2.3. Détermination de la décomposition par divisions euclidiennes successives

Si $n = \sum_{i=0}^k a_i b^i$ est la décomposition de $n$ en base $b$, et $n = r + bq$ est la division euclidienne de $n$ par $b$, on a $$a_0 = r \et q = \sum_{i=1}^k a_i b^{i-1}.$$ En particulier, si la décomposition de $n$ en base $b$ est $\underline{a_ka_{k-1}\dots a_1a_0}_b$, la décomposition de $q$ est $\underline{a_ka_{k-1}\dots a_1}_b$.

On veut écrire une fonction chiffres qui prend en arguments deux entiers $n\gt 0$ et $b\geq 2$ et renvoie une liste contenant les chiffres de la décomposition de $n$ en base $b$, du chiffre de plus gros poids au moins gros.

  1. Écrire un jeu de deux tests sur la fonction chiffres, testant les appels chiffres(5471, 10) et chiffres(2 ** 5 + 1, 2).
  2. Implémenter la fonction chiffres, d'une manière récursive.
  3. Implémenter la fonction chiffres, d'une manière itérative. On pourra utiliser l.reverse().
  4. ★ Implémenter une fonction chiffres_petit_boutiste utilisant une fonction récursive auxiliaire, sans renverser la liste.
Essayez :

2.4. Opérations en base $b$

Pour effectuer des opérations (addition, multiplication) à partir des décompositions en base $b$, on pose cette opération, et on procède comme pour des opérations décimales (retenues etc).

Faire les opérations suivantes, sur des décompositions binaires

  • $\begin{array}{cr} & 1\;\,1\;\,0\;\,0\;\,1\;\,1\;\,0\;\,0\;\,1 \\ + & 1\;\,1\;\,0\;\,0\;\,1\;\,0\;\,1\;\,0\end{array}$
  • $\begin{array}{cr} & 1\;\,1\;\,0\;\,0\;\,1\;\,1\;\,0\;\,0\;\,1 \\ - & 1\;\,1\;\,0\;\,0\;\,1\;\,0\;\,1\;\,0\end{array}$
  • $\begin{array}{cr} & 1\;\,0\;\,1\;\,1 \\ \times & 1\;\,0\;\,1\end{array}$

  1. Écrire une fonction addition_binaire qui prend en arguments deux listes l1 et l2 représentant l'écriture binaire petit-boutiste de deux entiers et qui renvoie une liste correspondant au résultat de l'addition binaire de l1 et l2.

    Pour simplifier, on pourra faire l'hypothèse que l1 et l2 ont la même longueur.

  2. ★ Écrire une fonction multiplication_binaire qui prend en arguments deux listes et réalise la multiplication. Elle utilisera la fonction précédente.
Essayez :

On représente une partie de $\db{1,n}$ par la liste de ses éléments. Implémenter une fonction partie_suivante qui prend en argument $n$ et une telle partie, et renvoie une nouvelle partie, de sorte que la fonction $f\colon \mc P(\db{1,n}) \ra \mc P(\db{1,n})$ correspondante soit un $2^n$-cycle.

3. Aspect pratique : représentation des entiers par la machine

3.1. Représentation des entiers naturels

Beaucoup de langages de programmation (ce n'est pas le cas de Python) disposent d'un type uint 2 (pour unsigned integer) pour représenter un entier positif à l'aide d'un mot de mémoire (donc de 64 ou 32 bits).

Comme un mot de 64 bits peut prendre $2^{64}$ valeurs différentes, ce type permet de représenter des entiers entre $0$ et $2^{64} - 1$. Un tel entier est représenté en mémoire par la liste de sa décomposition binaire, avec le bit de poids le plus fort en premier3, préfixé de zéros.

Sur une machine d'architecture 64 bits

  • L'entier non signé $3$ est représenté en mémoire par $\underbrace{0\dots0}_{62\text{ zéros}}11$
  • L'entier non signé $4$ est représenté par $\underbrace{0\dots0}_{61\text{ zéros}}100$
  • L'entier non signé $2^{64} - 1$ est représenté par $\underbrace{1 \dots 1}_{64\text{ uns}}$ car $2^{64} - 1 = \sum_{i=0}^{63} 2^i$.
  • Les entiers $\geq 2^{64}$ ne peuvent pas être représentés par un tel type uint.
  • Avec un tel type, il faut faire attention à l'éventuel débordement (overflow) des opérations élémentaires. Si le résultat d'une opération mathématique comme $a+b$, $a\times b$ ou $a-b$ n'appartient pas à $\db{0, 2^{64}-1}$, le résultat donné par la machine sera erroné. La machine renverra le reste du résultat correct dans la division euclidienne par $2^{64}$.

3.2. Représentation des entiers relatifs : codage en complément à 2

L'ensemble $\db{-2^{n-1}, 2^{n-1} -1}$ contient $2^{n-1}-1 - (-2)^{n-1} + 1 = 2^n$ éléments.

Le codage en complément à $2$ permet d'encoder tous les entiers de $\db{-2^{n-1}, 2^{n-1} -1}$ avec $n$ bits.

Pour coder un entier relatif $N\in \db{-2^{n-1}, 2^{n-1} -1}$.

  • Si $0\leq N \leq 2^{n-1}-1$ on utilise sa représentation binaire usuelle sur $n$ bits.
    Elle commence par un $0$.
  • Si $-2^{n-1}\leq N \lt 0$, on utilise la représentation binaire sur $n$ bits de $2^n + N = 2^n - |N| \in \db{2^{n-1}, 2^n - 1}$.
    Celle-ci commence par $1$.

Représenter $42$ et $-16$ sur $8$ bits par complément à $2$. Représenter $42 + (-16)$ sur $8$ bits. Que remarquez-vous ?

Quel est l'entier représenté en complément à $2$ sur $8$ bits 1. par $01101110$ ? 2. par $11101110$ ?

Le codage en complément à $2$ vérifie les propriétés suivantes.

  1. Le premier bit vaut $0$ si $N$ est positif, $1$ sinon.
  2. Deux entiers différents de $\db{-2^{n-1}, 2^{n-1} -1}$ ont des codages différents.
  3. Toute liste de taille $n$ composée de $0$ et de $1$ correspond au codage d'un entier de $\db{-2^{n-1}, 2^{n-1} -1}$.
  4. Si $N_1,N_2\in\db{-2^{n-1}, 2^{n-1} -1}$ et si $N_1 + N_2 \in \db{-2^{n-1}, 2^{n-1} -1}$, le codage de $N_1+N_2$ est obtenu en faisant la somme des codages de $N_1$ et $N_2$ via l'algorithme d'addition binaire usuel.

Les propriétés 2. et 3. signifient que cet encodage réalise une bijection entre $\db{-2^{n-1}, 2^{n-1} -1}$ et $\{0,1\}^n$.

Si $n\geq 0$ est représenté en complément à $2$ par les bits $a_1\dots a_{64}$, avec $a_{64} = 1$, quelle est la représentation de $-n$ ?

En général, la représentation de $-n$ s'obtient à partir de celle de $n$ en inversant tous les chiffres ($0\leftrightarrow 1$), puis en ajoutant $1$ au résultat obtenu, ce qui nécessite de faire l'addition, avec retenue.

En informatique, on représente un instant temporel par le nombre de secondes qui se sont écoulées à cet instant depuis le 1er janvier 1970. On représente ce nombre de secondes par un entier signé sur 32 bits. Quelle est approximativement l'année de la plus ancienne date qui puisse être représentée ? De la plus lointaine dans le futur ? (Connu sous le nom de bug de l'an 2038)

3.3. Le problème de dépassement (overflow)

Quelle que soit la représentation des entiers (signés ou non signés) sur $64$ bits, il existe des couples d'entiers $(a,b)$ dont la somme, la différence ou le produit ne peut pas être représenté avec $64$ bits. Dans ce cas, la machine effectue tout de même l'opération, mais ne garde que les $64$ bits les plus faibles du résultat.

Ce comportement est source d'un grand nombre de bugs historiques en informatique (le risque de dépassement sur des entiers de 64 bits est assez maigre, mais plus courant quand on utilise des entiers sur 8 bits par exemple).

En Python, ce n'est pas un problème, car le type utilisé pour les entiers utilise autant de mots mémoire que nécessaires pour représenter un entier donné. Les entiers de Python peuvent donc avoir une taille arbitraire. La contrepartie est que les opérations sur les entiers en Python peuvent être deux fois plus lentes que dans d'autres langages.

4. Les entiers de Python

Le type int de Python est plus complexe que les encodages précédents. D'une part parce que Python associe à chaque objet créé des informations supplémentaires, et d'autre part parce qu'il peut représenter des entiers relatifs arbitrairement grands/petits. Pour simplifier, on peut imaginer qu'en mémoire, un entier Python est représenté par autant de mots que nécessaires, selon sa taille.

L'avantage de cette représentation est que l'utilisateur n'a pas à se soucier des problèmes de débordement. L'inconvénient est que les opérations sont nettement plus lentes dans le language Python. Même pour des «petits» entiers, pour faire une opération élémentaire, la machine est obligée entre autres de faire un test sur le nombre de mots de leur représentation.

Pour de très grands entiers, on ne peut plus considérer les opérations élémentaires (addition/multiplication) comme ayant un coût constant. Par exemple, en entier de $256 = 8 \times 64$ bits est représenté sur $8$ mots machine, et l'addition de deux tels entiers utilise $8$ additions «élémentaires». En général, l'addition de deux entiers $\leq n$ serait en $O(\log_{2^{64}} n)$, et on peut imaginer que la multiplication est en $O\big(\log_{2^{64}}(n)^2\big)$.

5. Nombres dyadiques

Les nombres décimaux sont les réels dont le développement décimal contient un nombre fini de chiffres (après la virgule). Formellement, ce sont les réels $x$ qui peuvent s'écrire $$\begin{aligned}x & = \pm \big(a_q 10^q + a_{q-1} 10^{q-1} + \dots + a_0 10^0 + a_{-1} 10^{-1} + \dots + a_{-p} 10^{-p}\big) = \pm \sum\limits_{k=-p}^{q} a_k 10^k \\ &= \underline{a_q\dots a_0, a_{-1}\dots a_{-p}}_{10}\end{aligned}$$ où $p,q\in\N$ et $\forall i,\, a_i\in\db{0,9}$.

  • $12, 54 = 10^1 + 2\times 10^0 + 5 \times 10^{-1} + 4\times 10^{-2}$ est décimal
  • $\frac{1}{3} = 0{,}333\dots$ n'est pas un nombre décimal.

L'écriture $\frac{1}{3} = 0{,}3333\dots$ signifie formellement que $\frac{1}{3} = \lim\limits_{n\ra +\i}\sum_{k=1}^{n} \frac{3}{10^k} = \sum_{k=1}^{+\i} \frac{3}{10^k}$ (cf chapitre sur les séries).

Les nombres dyadiques sont les réels $x$ qui peuvent s'écrire $$\begin{aligned} x & = \pm \big(a_q 2^q + a_{q-1} 2^{q-1} + \dots + a_0 2^0 + a_{-1} 2^{-1} + \dots + a_{-p} 2^{-p}\big) = \pm \sum\limits_{k=-p}^{q} a_k 2^k \\ & = \underline{a_q\dots a_0, a_{-1}\dots a_{-p}}_{2}\end{aligned}$$ où $p,q\in\N$ et $\forall i,\,a_i\in\db{0,1}$.

Les nombres suivants sont dyadiques :

  • $0{,}25 = \frac{1}{4} = \frac{1}{2^2}$. On a donc $0{,}25 = \underline{0{,}01}_2$.
  • $3{,}375 =2^1 + 2^0 + \frac{1}{4} + \frac{1}{8}$. On a donc $3{,}375 = \underline{11{,}011}_2$.

Les nombres dyadiques sont exactement les nombres pouvant s'écrire comme $\frac{a}{2^b}$, pour $a\in\Z$ et $b\in\N$.

Si $x$ est dyadique, on peut écrire $$x = a_q 2^q + a_{q-1} 2^{q-1} + \dots + a_0 2^0 + a_{-1} 2^{-1} + \dots + a_{-p} 2^{-p} = \frac{1}{2^p} \left(a_q 2^{p+q} + a_{q-1} 2^{p+q-1} + \dots + a_{-p}\right) = \frac{N}{2^p},$$ avec $N\in\N$.

Réciproquement, si $x = \frac{a}{2^b}$ avec $a\in\Z$, on obtient un développement dyadique de $x$ en écrivant le développement binaire de $a$.

En particulier, comme $\frac{a}{2^b} = \frac{a 5^b}{10^b}$, tout nombre dyadique est décimal.

Développement dyadique

Le réel $0{,}1$ n'est pas un nombre dyadique.

On a $0,1 = \frac{1}{10}$, et cette fraction ne peut pas s'écrire sous la forme $\frac{a}{2^b}$.

En effet, si on avait $\frac{1}{10} = \frac{a}{2^b}$, on aurait $10 a = 2^b$, donc $2^b$ serait un multiple de $10 = 2\times 5$, ce qui n'est pas possible.

Le réel $0{,}1$ admet néanmoins un développement dyadique infini. Pour déterminer le développement dyadique d'un réel $x$, l'algorithme est le suivant.

  1. Si $x$ est négatif, on met un signe $-$ et on cherche le développement dyadique de $-x$.
  2. On cherche le développement binaire de la partie entière de $x$ (la partie avant la virgule), qu'on rajoutera au développement dyadique de la partie fractionnaire de $x$ (la partie après la virgule).
  3. Pour trouver le développement dyadique de $x\in \interval]{0, 1}[$, on répète les opérations suivantes :
    • On multiplie $x$ par $2$.
    • On prend la partie entière (donne un chiffre du développement dyadique).
    • On recommence avec la partie fractionnaire restante, qui donnera le chiffre suivant.

C'est le même algorithme que l'on utilise au collège pour donner le développement décimal d'une fraction comme $\frac{1}{3}$ :

  • On multiplie par $10$, on obtient $\frac{10}{3}$.
  • On retire la partie entière, qui vaut $3$. Il reste $\frac{1}{3}$.
  • On recommence.

On détermine le développement dyadique de $x = 0,1\in\interval]{0,1}[$.

  • On multiplie par $2$, on obtient $0{,}2$. La partie entière est $0$, donc le premier chiffre après la virgule est $0$.
  • On multiplie par $2$, on obtient $0{,}4$. La partie entière est $0$, donc le deuxième chiffre après la virgule est $0$.
  • On multiplie par $2$, on obtient $0{,}8$. La partie entière est $0$, donc le troisième chiffre après la virgule est $0$.
  • On multiplie par $2$, on obtient $1{,}6$. La partie entière est $1$, donc le quatrième chiffre après la virgule est $1$. La nouvelle partie fractionnaire est $0{,}6$
  • On multiplie par $2$, on obtient $1{,}2$. La partie entière est $1$, donc le cinquième chiffre après la virgule est $1$. La nouvelle partie fractionnaire est $0{,}2$
  • $\dots$

Finalement, on trouve un développement infini, mais périodique à partir du deuxième chiffre après la virgule : $$0{,}1 = \underline{0{,}00011001100110011\dots}_2$$

Écrire une fonction qui prend en argument un flottant $f\in\interval]{0,1}[$ et un entier $n$, et renvoie la liste des $n$ premiers chiffres après la virgule du développement dyadique de $f$.

6. Représentation des réels par la machine : les flottants

Les flottants sont utilisés pour représenter des nombres réels sur machine. Chaque flottant est encodé sur un mot de la mémoire, de 64 bits.

Un mot de la mémoire ne pouvant prendre que $2^{64}$ valeurs possibles, il n'existe que $2^{64}$ flottants possibles. Ces flottants correspondent à certains nombres dyadiques. Pour représenter un nombre réel $x$ qui n'est pas un nombre dyadique, on utilise une approximation dyadique de $x$.

$0{,}1 = \underline{0{,}00011001100110011\dots}_2$ n'étant pas un nombre dyadique, il est stocké en mémoire par une approximation dyadique, en tronquant son développement dyadique, par exemple.

Forme normalisée

Tout nombre décimal peut s'écrire sous la forme $\pm 1,a_1\dots a_k \times 10^e$.

Par exemple, $1678 = 1{,}678 \times 10^3$.

La propriété suivante est l'analogue de l'écriture scientifique pour la base $2$.

Tout nombre dyadique $x$ non nul admet une représentation de la forme $$x = \pm \underline{1,a_1\dots a_k}_2 \times 2^e,$$ où $e\in\Z$.

Cette forme est appelée la forme normalisée. Le nombre $e$ est appelé l'exposant, la partie $\underline{1,a_1\dots a_k}_2$ est appelée la mantisse.

On a vu que $3{,}375 =2^1 + 2^0 + \frac{1}{4} + \frac{1}{8}$ et $3{,}375 = \underline{11{,}011}_2$ donc $3{,}375 = \underline{1{,}1011}_2 \times 2^1$.

Représentation des flottants

On en présente ici une version simplifiée de l'encodage utilisé universellement pour représenter des flottants (norme IEEE 754).

Pour représenter un nombre dyadique $x = \pm \underline{1,a_1\dots a_k}_2 \times 2^e$ non nul à l'aide d'un mot de $64$ bits, on utilise

  • Le premier bit pour représenter le signe de $x$.

  • Les 11 bits suivants pour représenter l'exposant.

    En pratique, l'exposant n'est pas encodé par complément à $2$, mais par la représentation binaire de l'entier positif $e' = e+2^{10} -1 = e + 1023$.

  • Les 52 derniers bits pour représenter les chiffres après la virgule de la mantisse. La mantisse a donc au plus $52$ chiffres après la virgule.

Avec 11 bits, on pourrait en théorie encoder tous les exposants appartenant à $\db{-1023,1024}$, mais d'après la norme IEEE 754 les valeurs $e=-2013$ (donc $e' = 0$) et $e=1024$ (donc $e'=2047$) sont à interpréter différemment. Elles permettent entre autre de coder des flottants particuliers (comme $0$, NaN pour Not a Number, ou Inf pour infinity) dont l'étude est hors programme.

Le nombre $0$ est représenté de deux manières différentes, avec que des zéros sauf pour le bit de signe, qui peut valoir $1$. Il y a donc deux flottants nuls : 0.0 et -0.0.

Que représente $0|00001110011|100100000\dots$ ?

Pour représenter un nombre $x$ qui n'est pas dyadique, on tronque la mantisse de sa forme normale, pour ne garder que $52$ chiffres après la virgule.

On a vu que $$0{,}1 = \underline{0{,}00011001100110011\dots}_2 = 2^{-4}\times \underline{1{,}1001100110011\dots}_2.$$

La représentation binaire, sur $11$ bits, de $-4 + 2^{10} - 1 = 1019$ est $$1019 = 512 + 256 + 128 + 64 + 32 + 16 + 8 + 2 + 1 = \underline{01111111011}_2$$ La représentation machine de $0{,}1$ est donc $$0|01111111011|1001100110011001100110011001100110011001100110011001$$

  1. Le plus grand flottant représentable avec $64$ bits est $\underline{1{,}1111\dots 111}_2 \times 2^{1023} \simeq 2^{1024} \simeq 10^{308}$.
  2. Le plus petit flottant positif représentable avec $64$ bits est $\underline{1{,}0\dots 0}_2 \times 2^{-1022} = 2^{-1022}\simeq 10^{-308}$.

Comme la mantisse est encodée sur $52$ bits, un flottant n'a que $52$ «chiffres (binaires) significatifs».

On a $2^{-52}\simeq 10^{-17}$, donc la précision est d'environ $17$ chiffres décimaux.

En pratique, cela signifie que si $a,b$ sont deux réels tels que $|b|\leq \frac{|a|}{10^{17}}$ alors la représentation flottante de $a+b$ est la même que celle de $a$.

7. Quelques conséquences de la représentation inexacte des nombres réels

7.1. Phénomène d’absorption

La représentation flottante n'ayant que $52$ chiffres binaires significatifs, la représentation de $1$ est la même que celle de $1+2^{-60}$. De même, la représentation de $2^{100}$ comme flottant est la même que celle de $2^{100} + 1$.

Par contre, les entiers de Python étant multiprécision, ils n'ont pas ce problème. 

In [1]: a = 2. ** 100
In [2]: b = 2. ** 100 + 1.
In [3]: a-b
Out[3]: 0.0 # donc a=b ?
In [4]: a==b
Out[4]: True

In [1]: a = 2 ** 100
In [2]: b = 2 ** 100 + 1
In [3]: b-a
Out[3]: 1
In [4]: a==b
Out[4]: False

Conséquence : l'addition des flottants n'est pas associative : $(2^{100} - 2^{100}) + 1$ donne $1$, alors que $2^{100} - (2^{100} - 1)$ donne $0$.

7.2. Arithmétique inexacte

Les nombres non dyadiques, comme $0{,}1$, sont représentés par des approximations. La somme des approximations n'est pas égale à l'approximation de la somme. 

In [1]: 0.3 == 0.2 + 0.1
Out[1]: False

In [1]: 0.4 - 0.3 - 0.1
Out[1]: 2.7755575615628914e-17

In [1]: a = 10. ** 10
In [2]: (a+1)**2 - a**2 - 2*a - 1
Out[2]: -2049.0


In [1]: math.sqrt(2 ** 4) == 2 ** 2
Out[1]: True
In [2]: math.sqrt(2 ** 100) == 2 ** 50
Out[2]: False

7.3. Phénomène de compensation

Pour $\delta$ très proche de $0$, on veut calculer $1 - \sqrt{1-\delta}$. On sait que $1 - \sqrt{1-\delta}\simeq \frac{\delta}{2}$.

Algébriquement, on a $1 - \sqrt{1-\delta} = \frac{\delta}{1 + \sqrt{1-\delta}}$ (pourquoi ?). Dans l'extrait suivant, quel est le résultat le plus précis 4 ? On admettra que la fonction math.sqrt ne fait pas perdre de précision. 

In [1]: delta = 2 ** (-30)
In [2]: delta
In [2]: 1 - math.sqrt(1-delta)
Out[2]: 4.656612873077393e-10
In [4]: delta / (1 + math.sqrt(1-delta))
Out[4]: 4.656612874161595e-10

Notes de bas de page:

1

Un code RGB est codé sur 3 octets, donc $3\times 1080 \times 1920 \simeq 6\times 10^6$, soit 6 Mo. En pratique, un tel fichier image prend plutôt moins de 0.5 Mo, grâce à des encodages plus sophistiqués et des algorithmes de compression.

2

Son nom varie selon les langages et l'architecture. En C, il existe beaucoup de types d'entiers différents.

3

Représentation gros-boutiste. Pour certaines architectures, c'est l'inverse : on met les bits de poids les plus faibles en premier.

4

Le second calcul est plus précis. Dans le premier calcul, on commence par calculer $\sqrt{1-\delta}$ : la mantisse a une précision de $52$ chiffres binaires (ou $17$ chiffres décimaux), mais comme le résultat est très proche de $1$ (il vaut à peu près $1 - \frac{\delta}{2} \simeq 1 - 4\times 10^{-10}$) quand on le retire à $1$, il ne reste plus que $17-10\simeq 7$ chiffres significatifs décimaux. Dans le second calcul, le dénominateur est de l'ordre de $2$, connu avec $17$ chiffres significatifs, le résultat de l'opérateur garde une précision de $17$ chiffres significatifs.